package Tree_09.HeapSort_04;

/*
 * @Author 罗
 * @date 2020/3/22 - 11:06 上午
 *
 */

import java.util.Arrays;

public class HeapSort {


    public void headSort() {

    }

    /**
     * 堆排序的基本思想是：
     * (1)将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
     * (2)将其与末尾元素进行交换，此时末尾就为最大值。
     * (3)然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
     * 最后一个非叶子节点位置 =  length/2-1
     * 一个节点的右子节点是 2*n+2 ，当这个右子节点是最后一个节点时
     * 2*n+2 = length, 由此可以反推出最后一个非叶子节点
     * N = length/2-1
     * (n-1)/2 也可以通过子节点找到父节点
     *
     * @param array
     */
    public static void heapSort(int[] array) {
        int temp;

        /*
         * 最后一个非叶子节点
         * */
        /*int unLeafNodeIndex = array.length/2-1;
        HeapSort.adjustToBigHeap(array,unLeafNodeIndex,array.length);
        System.out.println("第一次调整"+ Arrays.toString(array));

        HeapSort.adjustToBigHeap(array,0,array.length);
        System.out.println("第二次调整"+Arrays.toString(array));*/

        /*
         * 封装
         * (1)将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
         *      第一次这样调整是因为 从堆的底部开始调整（调整所有元素）
         *
         * */
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjustToBigHeap(array, i, array.length);
        }
        /*
         * (3)然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
         *      length > 0 不可以是大于等于，否则adjustToBigHeap()会越界
         * int length = array.length - 1 -->为了不越界异常
         *                                  第一次进入交换的时候，完成后末尾只有一个排序好了的元素
         *                                        防止二次排序，到(2)交换的时候，出现不同步，等问题
         */
        for (int length = array.length - 1; length > 0; length--) {

            /*
             * (2)将其与末尾元素进行交换，此时末尾就为最大值。
             *      每次adjustToBigHeap()之后，本次length内的最大元素就被调整到了array[0]
             * */
            temp = array[length];
            array[length] = array[0];
            array[0] = temp;
            /*
             * 但是之后的调整都只用调整堆顶元素和末尾元素
             *   末尾元素是调整好的顺序(这里是较大的元素排在末尾)
             *       length逐渐递减是为了让已经调整好了的顺序不再参与adjustToBigHeap()
             *   相当于我们只用调节堆顶元素即可
             * */
            adjustToBigHeap(array, 0, length);
        }
    }

    /**
     * 将i对应的节点调整为大顶堆
     * 需要调用多次才能将指定长度的array调整为大顶堆
     *
     * @param unLeafNodeIndex 非叶子节点在数组中的索引
     * @param length          对多少个元素进行调整，length的长度应该在逐渐减小
     *                        没有在length范围内的元素是已经排序好的元素，不需要调整
     */
    public static void adjustToBigHeap(int[] array, int unLeafNodeIndex, int length) {
        /*
         * 先取出该非叶子节点的值并保存在临时变量中
         *
         * */
        int temp = array[unLeafNodeIndex];

        /*
         * (1)开始调整
         * i = unLeafNodeIndex * 2 + 1  -> 首先调整本非叶子节点的左节点
         * i = i * 2 + 1                -> 调整本非叶子节点的左节点的做节点，到length为止
         * */
        for (int k = unLeafNodeIndex * 2 + 1; k < length; k = k * 2 + 1) {
            /*
             * k + 1 < length 防止越界
             * */
            if (k + 1 < length && array[k] < array[k + 1]) {
                /*
                 * 左边节点小于右边节点
                 * 将k指向右子节点，指向较大的那一个值
                 * */
                k++;
            }
            /*
             * (2)先比较左右子节点，再把左右子节点中值较大的那一个和父节点比较
             * 此时k已经指向了左右子节点较大的那一个值
             * */
            if (array[k] > temp) {
                /*
                 * 子节点的值大于父节点
                 *   进行交换
                 *      将较大的节点的值赋值给父节点
                 * */
                array[unLeafNodeIndex] = array[k];
                /*
                 * unLeafNodeIndex指向k，继续循环比较
                 * */
                unLeafNodeIndex = k;
            } else {
                /*
                 * (3)左右子节点的最大值 <= 父节点，直接退出，进行交换
                 * 因为调整是从下到上，从左到右调整的，本非叶子节点的的子节点已经是叶子节点
                 * 即本非叶子节点不存在孙节点
                 * 所以可以直接跳出
                 * 2.如果是之后调用此方法，本非叶子节点已经有孙节点或者以上，依旧可以
                 *
                 * */
                break;
            }
        }
        /*
         * 当for循环结束，我们已经将以unLeafNodeIndex为父节点树的最大值放在了unLeafNodeIndex上
         *       但是还没有将unLeafNodeIndex的值写入到子节点
         * 因为经过了 unLeafNodeIndex = k;
         * 此时unLeafNodeIndex指向的是左右子节点中值比父节点大的位置
         * 将父节点的值（如果发生交换，则子节点的值比父节点的值大，如果没有发生交换（父节点的值最大），此次赋值就无效）
         *       赋值给子节点
         * */
        array[unLeafNodeIndex] = temp;
    }

    /**
     * @param countBackwards 树的倒数第几个元素，树对应数组，都是从下标0开始计数
     */
    @Deprecated
    private void toBigHeap(int[] array, int countBackwards) {
        if (countBackwards < 0) {
            return;
        }

        int temp;
        int unLeafNode = 0;
        /*
         * 防止到达根节点时，还调用父节点，计算出父节点的下标是-1，越界异常
         */
        if (countBackwards != 0) {
            /*
             * 第一次调用 = 获取最后一个非叶子节点
             * 其余次调用，获取本节点的父节点
             * */
            unLeafNode = countBackwards / 2 - 1;
        }
        /*
         * 比较非叶子节点的两个子节点的值
         * */
        if (array[unLeafNode * 2 + 1] > array[unLeafNode * 2 + 2]) {
            /*
             * 到达根节点unLeafNode == 0，且已经是根节点最大，就将结果返回
             * */
            if (unLeafNode == 0 && array[unLeafNode] >= array[unLeafNode * 2 + 1]) {
                return;
            }

            /*
             * 左边节点的值比较大
             * 将左边节点的值和本非叶子节点的值交换
             * */
            temp = array[unLeafNode];
            array[unLeafNode] = array[unLeafNode * 2 + 1];
            array[unLeafNode * 2 + 1] = temp;
        } else {
            if (unLeafNode == 0 && array[unLeafNode] >= array[unLeafNode * 2 + 2]) {
                return;
            }

            /*
             * 右边节点的值比较大
             * 将右边节点的值和本非叶子节点的值交换
             */
            temp = array[unLeafNode];
            array[unLeafNode] = array[unLeafNode * 2 + 2];
            array[unLeafNode * 2 + 2] = temp;
        }
        /*
         * 进行递归，到本非叶子节点的上一个节点
         * */
        toBigHeap(array, (unLeafNode - 1) / 2);

    }


}
